Vào năm 1895, Ủy ban châu Phi của Pháp đã có một dự án xây dựng nhà thờ Hồi giáo nhưng không thành công.

Đến năm 1916, quyết định xây dựng Nhà thờ Hồi giáo Paris được phê duyệt sau Trận Verdun. Tại trận chiến này đã có 50.000 binh lính Hồi giáo thiệt mạng và trong Chiến tranh thế giới thứ nhất, tổng cộng 100.000 binh lính Hồi giáo hy sinh vì nước Pháp.

Việc xây dựng được bắt đầu năm 1922 với kinh phí do nhà nước Pháp cấp, việc xây dựng do người Ả Rập thực hiện. Nhà thờ này nằm trên vị trí của bệnh viện Pitié cũ, gần vườn Plantes de Paris, thuộc khu vực trung tâm.

Lấy cảm hứng từ Nhà thờ Hồi giáo Quaraouiyine ở Fès, một trong những nhà thờ Hồi giáo quan trọng nhất Maroc, tất cả phần trang trí ghép mảnh được các thợ thủ công Bắc Phi thực hiện. Tháp nhà thờ cao 33 mét, mô phỏng theo Nhà thờ Kairouan ở Tunisia. Cửa lớn trang trí hoa theo phong cách thuần Hồi giáo. Nhà thờ này cũng bao gồm một phòng cầu kinh, một madrasa (trường học kiểu Hồi giáo), một thư viện, một phòng họp cùng nhà hàng, phòng uống trà, phòng tắm hơi, các cửa hàng.

Trong Chiến tranh thế giới thứ hai, khi Paris bị Quân đội Đức chiếm đóng, nhà thờ này là địa điểm của lực lượng kháng chiến Hồi giáo tại Pháp.